package prime;

import java.math.BigInteger;
import java.util.Random;

import util.Util;

public class Fermat {

	public static boolean isPrime(BigInteger n, int k)
	{
		Random rnd = Util.getRnd();
		for(int i = 0; i < k; ++i)
		{
			BigInteger a = new BigInteger(n.bitCount(), rnd).mod(n.subtract(Util.ONE)).add(Util.ONE);
			if(a.modPow(n.subtract(Util.ONE), n).compareTo(Util.ONE) != 0)
				return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
		for(int i = 5; i < 100; ++i)
			if(isPrime(BigInteger.valueOf(i), 5000))
				System.out.println(i);
		System.out.println("Done!");
	}

}
